import java.util.ArrayList;
import java.util.List;

//太平洋大西洋水流问题
//测试链接：https://leetcode.cn/problems/pacific-atlantic-water-flow/
public class PacificAtlantic {
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    int n, m;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        n = heights.length; m = heights[0].length;
        boolean[][] vis1 = new boolean[n][m];
        boolean[][] vis2 = new boolean[n][m];
        List<List<Integer>> ans = new ArrayList<>();

        for(int i = 0; i < m; i++){
            dfs(heights, 0, i, vis1); //第一行
            dfs(heights, n-1, i, vis2); //最后一行
        }
        for(int i = 0; i < n; i++) {
            dfs(heights, i, 0, vis1); //第一列
            dfs(heights, i, m-1, vis2); //第二列
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(vis1[i][j] && vis2[i][j]) {  //表示能流向太平洋又能流向从大西洋
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i); temp.add(j);
                    ans.add(temp);
                }
            }
        }

        return ans;
    }

    public void dfs(int[][] heights, int i, int j, boolean[][] vis) {
        vis[i][j] = true;
        for(int k = 0; k < 4; k++) {
            int x = dx[k] + i;
            int y = dy[k] + j;
            if(x >= 0 && x < n && y >= 0 && y < m &&
                    !vis[x][y] && heights[x][y] >= heights[i][j]) {
                dfs(heights,x,y,vis);
            }
        }
    }
}
